package com.itheima.leetcode.od.c.graph;

import java.util.*;
import java.util.stream.Collectors;

/**
 * <h3>迷宫问题</h3>
 */
public class DFSMaze {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 处理输入
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        // 初始化迷宫矩阵
        int[][] matrix = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }

        // 初始化变量
        minStep = n * m;
        boolean[][] visited = new boolean[n][m];
        visited[0][0] = true;
        currentPath.add(new Pair<>(0, 0));

        // 开始搜索
        dfs(0, 0, matrix, visited);

        // 输出结果
        System.out.println(minPath.stream()
                .map(pair -> "(" + pair.first + "," + pair.second + ")")
                .collect(Collectors.joining("\n")));

        scanner.close();
    }

    // 定义全局变量
    static int minStep;
    static List<Pair<Integer, Integer>> currentPath = new ArrayList<>();
    static List<Pair<Integer, Integer>> minPath = new ArrayList<>();
    // 四个方向：下、右、上、左
    static List<Pair<Integer, Integer>> direction = Arrays.asList(
            new Pair<>(1, 0),
            new Pair<>(0, 1),
            new Pair<>(-1, 0),
            new Pair<>(0, -1)
    );

    static class Pair<T, U> {
        T first;
        U second;

        public Pair(T first, U second) {
            this.first = first;
            this.second = second;
        }
    }

    static void dfs(int x, int y, int[][] matrix, boolean[][] visited) {
        int line = matrix.length;
        int col = matrix[0].length;

        // 到达右下角终点
        if (x == line - 1 && y == col - 1) {
            if (minStep > currentPath.size()) {
                minStep = currentPath.size();
                minPath.clear();
                minPath.addAll(currentPath);
            }
            return;
        }

        // 遍历四个方向
        for (int i = 0; i < direction.size(); i++) {
            int nextx = x + direction.get(i).first;
            int nexty = y + direction.get(i).second;

            // 检查是否超出范围
            if (nextx >= line || nextx < 0 || nexty >= col || nexty < 0) {
                continue;
            }

            // 检查是否可以访问
            if (matrix[nextx][nexty] == 0 && !visited[nextx][nexty]) {
                visited[nextx][nexty] = true;
                currentPath.add(new Pair<>(nextx, nexty));
                dfs(nextx, nexty, matrix, visited);
                visited[nextx][nexty] = false;
                currentPath.remove(currentPath.size() - 1);
            }
        }
    }
}